package com.dyz.leetcode._03_mathematics;

public class _233_countDigitOne {

    //超时
    public int countDigitOne1(int n) {
        int res = 0;
        for(int i=1; i<=n;i++){
            String s = String.valueOf(i);
            int tmp = 0;
            for(char ch:s.toCharArray()){
                if(ch=='1'){tmp++;}
            }
            res+=tmp;
        }
        return res;
    }
    //动态规划 内存爆掉
     public int countDigitOne2(int n) {
     int ans = 0;
     int[] dp = new int[n + 1];
     dp[1] = 1;
     for (int i = 1; i <= n; i++) {
         dp[i] = dp[i % 10] + dp[i / 10];
         ans += dp[i];
     }
     return ans;
     }
     //找规律
    public int countDigitOne(int n) {
        int res = 0;
        for(int i=1; i<=n; i=i*10){
            res += (n/(i*10))*i+Math.min(Math.max(n%(i*10)-i+1,0),i);
        }
        return res;
    }
}
